package com.love.labuladong.str;

/**
 * @Author : zh
 * @Description : 不停删除之后剩下的字符串
 *
 *  给定一个字符串s1，如果其中含有S2字符串，就删除最左出现的那个，删除之后s1剩下的字符重新拼接在一起，再删除最左出现的那个，
 *  如此周而复始，返回最终剩下的字符串
 *
 *  s1: xababccyabca
 *  s2: abc
 *
 *  res: xabcyabca -> xyabca -> xya
 *
 *
 * @Date : 2024-08-26 15:36
 */
public class Kmp_deleteStr {

    public static int MAXN = 1000001;

    public static int[] stack1 = new int[MAXN];

    public static int[] stack2 = new int[MAXN];

    // 栈的大小
    public static int top;



    public static void compute(char[] s1,char[] s2){
        top = 0;
        int n = s1.length;
        int m = s2.length;
        int x = 0, y = 0;
        int[] next = KMP.nextArray(s2, m);
        while ( x < n){
            if(s1[x] ==  s2[y]){
                stack1[top] = x;
                stack2[top] = y;
                top++;
                x++;
                y++;
            }else if(y == 0){
                stack1[top] = x;
                stack2[top] = -1;
                top++;
                x++;
            }else {
                y = next[y];
            }
            if(y == m){
                top -= m;
                y = top > 0 ? (stack2[top - 1] + 1) : 0;
            }
        }

    }



}
